//import com.sun.org.apache.xpath.internal.objects.XNodeSet;
//class ListNode {
//    public int val;
//    public ListNode next;//  节点类型
//
//    public ListNode(int val) {//构造方法
//        this.val = val;
//    }
//
//}
//
//public class MyLinkedList {
//    public ListNode next;//  链表的头引用
//    public ListNode head;
//
//
//    //创建一个链表  很low  穷举法
//    public void createList() {
//        ListNode listNode1 = new ListNode(12);
//        ListNode listNode2 = new ListNode(23);
//        ListNode listNode3 = new ListNode(34);
//        ListNode listNode4 = new ListNode(45);
//        ListNode listNode5 = new ListNode(56);
//
//        listNode1.next = listNode2;
//        listNode2.next = listNode3;
//        listNode3.next = listNode4;
//        listNode4.next = listNode5;
//        this.head = listNode1;
//    }
//
//    /*public static void main(String[] args) {
//        ListNode listNode = new ListNode(1);//实例化一个节点
//    }*/
//
//    // 1、无头单向非循环链表实现
//    // 查找是否包含关键字key是否在单链表当中
//    public boolean contains(int key) {
//        ListNode cur = this.head;
//        while (cur != null) {
//            if (cur.val == key) {
//                return true;
//            }
//            cur = cur.next;
//        }
//        return false;
//    }
//
//    //任意位置插入,第一个数据节点为0号下标
//    public boolean addIndex(int index, int data) {
//        if (index < 0 || index > size()) {
//            System.out.println("index位置不合理");
//        }
//        if (index == 0) {
//            addFirst(data);//头插法
//            return true;
//        }
//        if (index == size()) {
//            addLast(data);//尾插法
//            return true;
//        }
//        ListNode cur = findIndex(index);
//        ListNode node = new ListNode(data);
//        node.next = cur.next;
//        cur.next = node;
//        return true;
//    }
//
//
//    public ListNode findIndex(int index) {
//        ListNode cur = this.head;
//        while (index - 1 != 0) {
//            cur = cur.next;
//            index--;
//        }
//        return cur;
//    }
//
//    //得到单链表的长度
//    public int size() {
//        int count = 0;
//        ListNode cur = this.head;
//        while (cur != null) {
//            count++;
//            cur = cur.next;
//        }
//        return count;
//    }
//
//
//    //头插法*************绑定位置的时候一定要先绑定后边，这样后面才不会丢********
//    public void addFirst(int data) {
//        ListNode node = new ListNode(data);
//        node.next = this.head;//不能写反了和下面
//        this.head = node;
//    }
//
//    //尾插法 从头开始找尾巴   第一次插入必须判断链表是否为空
//    public void addLast(int data) {
//        ListNode cur = this.head;
//        ListNode node = new ListNode(data);
//        if (this.head != null) {
//            cur = cur.next;
//            while (cur.next == null) {
//                cur.next = node;
//            }
//        }
//        this.head = node;
//    }
//
//
//    public ListNode searchPerv(int key) {//找到key的   前趋 前趋 前趋 前趋
//        ListNode cur = this.head;
//        while (cur.next != null) {
//            if (cur.next.val == key) {
//                return cur;
//            }
//            cur = cur.next;
//        }
//        return null;
//    }
//
//    //删除第一次出现关键字为key的节点
//    public void remove(int key) {
//
//        if (this.head == null) {
//            System.out.println("单链表为空，不能删除！");
//            return;
//        }
//        if (this.head.val == key) {//删除的对象是头节点
//            this.head = this.head.next;
//            return;
//        }
//        ListNode cur = searchPerv(key);
//        if (cur == null) {
//            System.out.println("没有你要删除的节点");
//        }
//        ListNode del = cur.next;
//        cur.next = del.next;
//    }
//
//
//    //删除所有值为key的节点,遍历链表一遍**笔试难度****
//    public ListNode removeAllKey(int key) {
//        ListNode prev = this.head;
//        ListNode cur = this.head.next;
//        if (this.head == null) {
//            return null;
//        }
//        while (cur != null) {
//            if (cur.val == key) {
//                prev = cur.next;
//                cur = cur.next;
//            } else {
//                prev = cur;
//                cur = cur.next;
//            }
//        }
//        if (this.head.val == key) {//删除头节点
//            this.head = this.head.next;
//        }
//        return this.head;
//    }
//
//
//    //**********反转链表**************
//    public ListNode reverseList() {
//        if (this.head == null) {//判断头节点是否为空
//            return null;
//        }
//        ListNode prev = null;
//        ListNode cur = this.head;
//        while (cur != null) {
//            ListNode curNext = cur.next;//存储下一个节点的位置
//            cur.next = prev;
//            prev = cur;
//            cur = curNext;
//        }
//        return prev;//到最后 新的头节点
//    }
//
//
//    //***********找到链表的中间位置********偶数的话找到中间的第一个*****
//    public ListNode middleSearch() {
//        if (this.head == null) {
//            return null;
//        }
//        ListNode slow = this.head;
//        ListNode fast = this.head;
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            if (fast == null) {// 偶数情况：返回中间的第一个
//                return slow;
//            }
//            slow = slow.next;
//        }
//        return slow;
//    }
//
//
//    //**********查找链表中倒数第K个***********
//    public ListNode countdownSearch(int k) {
//        if (k <= 0 || this.head == null) {
//            return null;
//        }
//        ListNode slow = this.head;
//        ListNode fast = this.head;
//        while (k - 1 != 0) {//  fast先正向移动k-1步
//            fast = fast.next;
//            if (fast == null) {
//                return null;
//            }
//            k--;
//        }
//        while (fast.next != null) {//再让slow和fast 同时正向移动 直到fast.next = null，此时的slow就是倒数第k个
//            fast = fast.next;
//            slow = slow.next;
//        }
//        return slow;
//    }
//
//
//    //********给定一个X值，将链表所有小于X的值排在所有大于等于X的值之前，且原顺序不变**************
//    public ListNode partition(int x) {
//        ListNode bs = null;
//        ListNode be = null;
//        ListNode as = null;
//        ListNode ae = null;
//        ListNode cur = this.head;
//        while (cur != null) {
//            if (cur.val < x) {
//                //在X左边第一次插入
//                if (bs == null) {
//                    bs = cur;
//                    be = cur;
//                } else {
//                    //不是第一次  尾插法
//                    be.next = cur;
//                    be = be.next;
//                }
//            } else {
//                if (as == null) {
//                    //在X右边第一次插入
//                    as = cur;
//                    ae = cur;
//                } else {
//                    //不是第一次  尾插法
//                    ae.next = cur;
//                    ae = ae.next;
//                }
//            }
//            cur = cur.next;
//        }
//        if (bs == null) {//x的左边可能没有数据
//            return as;
//        }
//        be.next = as;
//        if (as != null) {
//            ae.next = null;
//        }
//        return bs;
//    }
//
//
//    //**********将一个有序链表的所有重复的节点删除***********
//    public ListNode deleteDuplication() {
//        ListNode cur = this.head;
//        ListNode newHead = new ListNode(-1);//创建一个虚拟节点，将链表*不重复*的节点全部接在后面
//        ListNode tmp = newHead;
//        while (cur != null) {
//            if (cur.val == cur.next.val && cur.next != null) {
//                while (cur.val == cur.next.val && cur.next != null) {//头节点和尾节点都有可能重复
//                    cur = cur.next;
//                }
//                //多走一步
//                cur = cur.next;
//            } else {
//                tmp.next = cur;
//                tmp = tmp.next;
//                cur = cur.next;
//            }
//        }
//        //防止最后一个节点也是重复的
//        tmp.next = null;
//        return newHead.next;
//    }
//
//
//    //*********判断是否为回文数*************
//    public boolean PalindromeList() {
//        ListNode fast = this.head;
//        ListNode slow = this.head;
//        if (this.head == null) {
//            return true;
//        }
//
//        //fast走两步，slow走一步， slow走到中间位置
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        //开始反转
//        ListNode cur = slow.next;
//        while (cur != null) {
//            ListNode curNext = cur.next;
//            cur.next = slow;
//            slow = cur;
//            cur = curNext;
//        }
//
//        while (head != slow) {
//            if (head.val != slow.val) {//奇数情况
//                return false;
//            }
//            if (head.next == slow) {//偶数情况
//                return true;
//            }
//            head = head.next;
//            slow = slow.next;
//        }
//        return true;
//    }
//
//
//    //*************找出两个链表的公共节点******************
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        if (headA == null || headB == null) {
//            return null;
//        }
//        //pl永远指向最长的链表，ps永远指向最短的
//        ListNode pl = headA;//假定为最长，B为最短，后面在判断
//        ListNode ps = headB;
//        int lenA = 0;//初始两个链表的长度
//        int lenB = 0;
//        while (pl != null) {
//            lenA++;
//            pl = pl.next;
//        }
//        pl = headA;
//        while (ps != null) {
//            lenB++;
//            ps = ps.next;
//        }
//        ps = headB;
//        int len = lenA - lenB;//求链表的差值
//        if (len < 0) {
//            pl = headB;
//            ps = headA;
//            len = lenB - lenA;
//        }
//        while (len != 0) {//pl先走len步
//            pl = pl.next;
//            len--;
//        }
//        while (pl != ps) {//pl，ps同时走，直到相等
//            pl = pl.next;
//            ps = ps.next;
//        }
//        return pl;
//    }
//
//
//    //************判断一个列表是否有环********************
//    public boolean hasCycle(ListNode head) {
//        if (head == null) {
//            return false;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if (fast == slow) {
//                return true;
//            }
//        }
//        return false;
//    }
//
//    //*******一个个释放****************
//    public void clear() {
//        while (this.head != null) {
//            ListNode curNext = head.next;
//            this.head.next = null;//找不到下一个数据的位置
//            this.head = curNext;
//        }
//    }
//
//
//    public void display() {//打印
//        ListNode cur = this.head;
//        while (cur != null) {
//            System.out.print(cur.val + " ");
//            cur = cur.next;
//        }
//        System.out.println();
//    }
//
//    public void display2(ListNode newHead) {//从指定位置打印
//        ListNode cur = newHead;
//        while (cur != null) {
//            System.out.print(cur.val + " ");
//            cur = cur.next;
//        }
//        System.out.println();
//    }
//
//}
//

